﻿#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable : 4996)
#pragma warning(disable : 6031)

//LeetCode 88 合并两个有序数组

//给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
//请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
//注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。
//为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。


//(方法一) ：先将nums2数组接到nums1中，再排序
//int cmp_int(int* e1, int* e2)
//{
//    return *e1 - *e2;
//}
//
//void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
//{
//    int i = 0;
//    for (i = 0; i < n; i++)
//    {
//        nums1[i + m] = nums2[i];
//    }
//    qsort(nums1, n + m, sizeof(int), cmp_int);
//}

//(方法二):双指针，因为两个数组本来就是有序的
// 这里为了防止覆盖的产生，我们从新开辟了一个新数组
//void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
//{
//    int sort[200] = { 0 };
//    int v = 0;
//    int i = 0;
//    int j = 0;
//    while (v < n + m)
//    {
//        if (i == m)
//        {
//            sort[v] = nums2[j];
//            j++;
//        }
//        else if (j == n)
//        {
//            sort[v] = nums1[i];
//            i++;
//        }
//        else if (nums1[i] >= nums2[j])
//        {
//            sort[v] = nums2[j];
//            j++;
//        }
//        else
//        {
//            sort[v] = nums1[i];
//            i++;
//        }
//        v++;
//    }
//    memcpy(nums1, sort, sizeof(int) * (n + m));
//}

//******(err)******
//void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
//{
//    int sort[200] = { 0 };
//    int v = 0;
//    int i = 0;
//    int j = 0;
//    while (v < n + m)
//    {
//        if (i == m || nums1[i] >= nums2[j])    //与上面的不同，这里将sort[v] = nums2[j]的条件放在了一起
//        {										 //但是若有一个数组遍历完成，那么这个数组再进行比较大小
//            sort[v] = nums2[j];				 //就会造成越界访问
//            j++;
//        }
//        else if (j == n || nums1[i] < nums2[j])
//        {
//            sort[v] = nums1[i];
//            i++;
//        }
//        v++;
//    }
//    memcpy(nums1, sort, sizeof(int) * (n + m));
//}

//方法三：逆向双指针 两个数组都有序
//我们将两个数组从后往前遍历，比较两者每个元素的大小
//在第一个数组中将较大值从后往前放，这样可以防止覆盖

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
    int v = m + n - 1;  //记录数组nums1最后一个下标
    int i = m - 1;      //记录数组nums1中开始有数据的最末尾的下标
    int j = n - 1;      //记录数组nums2中开始有数据的最末尾的下标
    while (i >= 0 || j >= 0)
    {
        if (i == -1)
        {
            nums1[v] = nums2[j];
            j--;
        }
        else if (j == -1)
        {
            nums1[v] = nums1[i];
            i--;
        }
        else if (nums1[i] > nums2[j])
        {
            nums1[v] = nums1[i];
            i--;
        }
        else
        {
            nums1[v] = nums2[j];
            j--;
        }
        v--;
    }
}
